struct ListNode* partition(struct ListNode* head, int x) {
    struct ListNode* lessGuard = (struct ListNode*)malloc(sizeof(struct ListNode));
    lessGuard->next = NULL;
    struct ListNode* lesstail = lessGuard;
    struct ListNode* greaterGuard = (struct ListNode*)malloc(sizeof(struct ListNode));
    greaterGuard->next = NULL;
    struct ListNode* greatertail = greaterGuard;
    struct ListNode* cur = head;
    while (cur)
    {
        if (cur->val < x)
        {
            lesstail->next = cur;
            lesstail = lesstail->next;
        }
        else
        {
            greatertail->next = cur;
            greatertail = greatertail->next;
        }
        cur = cur->next;
    }
    greatertail->next = NULL;
    lesstail->next = greaterGuard->next;
    free(greaterGuard);
    head = lessGuard->next;
    free(lessGuard);
    return head;
}